package com.leetcode.no84;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int res = 0;

        if (len == 0) {
            return res;
        }
        if (len == 1) {
            return heights[0];
        }

        // 遍历每个柱子，以当前柱子的高度作为矩形的高 h，
        // 从当前柱子向左右遍历，找到矩形的宽度 w。
        for (int i = 0; i < len; i++) {
            int w = 1, h = heights[i];

            // 向左找边界
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] >= h) {
                    w++;
                }
            }

            // 向右找边界
            for (int j = i + 1; j <= len - 1; j++) {
                if (heights[j] >= h) {
                    w++;
                }
            }
            res = Math.max(res, w * h);
        }
        return res;
    }

    HashMap<String, Integer> map;

    public int largestRectangleArea01(int[] heights) {
        int len = heights.length;
        int res = 0;


        if (len == 0) {
            return res;
        }
        if (len == 1) {
            return heights[0];
        }


        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                res = Math.max(res, getArea(heights, i, j));
            }
        }
        return res;
    }

    private int getArea(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }

        // 找到最小的值
        int min = Integer.MAX_VALUE;
        for (int i = left; i <= right; i++) {
            min = Math.min(min, arr[i]);
        }

        return min * (right - left + 1);
    }

//    private void getMinMap(int[] arr){
//        for(int i = 0; i<arr.length;i++){
//            map.put(new String(i+""+i));
//            for(int j = i+1; j<arr.length; j++){
//                if()
//                int min = Integer.MAX_VALUE;
//
//            }
//        }
//    }

    public static void main(String[] args) {
        Solution s1 = new Solution();
        int res = s1.largestRectangleArea01(new int[]{2, 1, 5, 6, 2, 3});
        System.out.println(res);
    }
}


// 把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最戳出来的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
//
//这个算法的关键点是把那些戳出来的木板早点单独拎出来计算，然后就用不着这个值了。


class Solution01 {
    public int largestRectangleArea(int[] heights) {
        //暴力破解
        int max = 0, n = heights.length;
        for (int i = 0; i < n; i++) {     //枚举以当前heights[i]为高的所有矩形
            int temp = 0;
            for (int k = 0; k <= i; k++) {    //遍历前半部分，加上紧邻当前heights[i]的可用矩形面积
                if (heights[k] >= heights[i])
                    temp += heights[i];
                else
                    temp = 0;
            }
            for (int j = i + 1; j < n; j++) {     //遍历后半部分
                if (heights[j] < heights[i])
                    break;                  //因为遍历后半部分可以截断，所以前后部分遍历分开写了
                else {
                    temp += heights[i];
                }
            }
            if (max < temp)
                max = temp;
        }
        return max;
    }
}


// 最小栈解法
class Solution02 {
    public int largestRectangleArea01(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }

        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        return ans;
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int res = 0;

        if (len == 0) {
            return res;
        }
        if (len == 1) {
            return heights[0];
        }

        // 单调栈  存放的是索引值
        Stack<Integer> mono_stack = new Stack<Integer>();

        // 向左找下一个更小值
        for (int i = 0; i < len; i++) {
            // 维护一个栈
            // 栈中的元素是 从栈底到栈顶 由小到大
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()]) {
                // 高个子别挡道，我heights[i]要找比我矮的妹妹！
                mono_stack.pop();
            }

            // 在左边找到了比我矮的妹妹吗？
            left[i] = mono_stack.isEmpty() ? -1 : mono_stack.peek();
            mono_stack.push(i);
        }

        mono_stack.clear();

        // 向右找下一个更小值
        for (int i = 0; i < len; i++) {
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()]) {
                int preIndex = mono_stack.pop();
                right[preIndex] = i;
            }

            mono_stack.push(i);
        }
        while (!mono_stack.isEmpty()) {
            right[mono_stack.pop()] = len;
        }

        for (int i = 0; i < len; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }

        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};
        Solution02 s1 = new Solution02();

        System.out.println(s1.largestRectangleArea(arr));
        System.out.println(s1.largestRectangleArea(arr01));

        System.out.println("------------------------------");
        System.out.println(s1.largestRectangleArea01(arr));
        System.out.println(s1.largestRectangleArea01(arr01));
    }


}


// 最小栈解法 单调栈 + 常数优化
class Solution03 {
    public int largestRectangleArea01(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        Stack<Integer> mono_stack = new Stack<Integer>();

        for(int i=0;i<n;++i){
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i] ){
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }

            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }

        return ans;
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int res = 0;

        if (len == 0) {
            return res;
        }
        if (len == 1) {
            return heights[0];
        }

        // 单调栈  存放的是索引值
        Stack<Integer> mono_stack = new Stack<Integer>();

        // 向左找下一个更小值
        for (int i = 0; i < len; i++) {
            // 维护一个栈
            // 栈中的元素是 从栈底到栈顶 由小到大
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()]) {
                // 高个子别挡道，我heights[i]要找比我矮的妹妹！
                mono_stack.pop();
            }

            // 在左边找到了比我矮的妹妹吗？
            left[i] = mono_stack.isEmpty() ? -1 : mono_stack.peek();
            mono_stack.push(i);
        }

        mono_stack.clear();

        // 向右找下一个更小值
        for (int i = 0; i < len; i++) {
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()]) {
                int preIndex = mono_stack.pop();
                right[preIndex] = i;
            }

            mono_stack.push(i);
        }
        while (!mono_stack.isEmpty()) {
            right[mono_stack.pop()] = len;
        }

        for (int i = 0; i < len; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }

        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};
        Solution02 s1 = new Solution02();

        System.out.println(s1.largestRectangleArea(arr));
        System.out.println(s1.largestRectangleArea(arr01));

        System.out.println("------------------------------");
        System.out.println(s1.largestRectangleArea01(arr));
        System.out.println(s1.largestRectangleArea01(arr01));
    }


}


// 思路 找到右边第一个比它大的值的index
class FindRightFirstBigger {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由大到小 遇上更大的 弹出来  更大的压进去
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                // 意味着i是preIndex的下一个更大值
                int preIndex = stack.pop();

                ans[preIndex] = i;
            }

            // 压入i
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        FindRightFirstBigger f1 = new FindRightFirstBigger();

        System.out.println(Arrays.toString(f1.work(arr)));

    }
}

// 找到右边第一个比它小的元素
class FindRightFirstSmaller {
    public int[] work(int[] arr) {

        int len = arr.length;
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由小到大 遇上更小的  栈全弹出来  更小的压进去
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                // 意味着i是preIndex的下一个更大值
                int preIndex = stack.pop();

                ans[preIndex] = i;
            }

            // 压入i
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        FindRightFirstSmaller f1 = new FindRightFirstSmaller();

        System.out.println(Arrays.toString(f1.work(arr)));

    }
}


// 思路 找到左边第一个比它大的值的index
class FindLeftFirstBigger {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();  // 这里放元素索引 而不是元素
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由大到小
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                // 矮个子出列
                stack.pop();
            }

            // 这个元素
            ans[i] = stack.empty() ? -1 : stack.peek();

            // 压入i 接收后面身高的审判吧
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};

        FindLeftFirstBigger f1 = new FindLeftFirstBigger();

        System.out.println(Arrays.toString(f1.work(arr)));
        System.out.println(Arrays.toString(f1.work(arr01)));

    }
}


// 思路 找到左边第一个比它小的值的index
class FindLeftFirstSmaller {
    public int[] work(int[] arr) {
        int len = arr.length;

        Stack<Integer> stack = new Stack<>();  // 这里放元素索引 而不是元素
        int[] ans = new int[len];

        // 维护一个栈
        // 栈中的元素是 从栈底到栈顶 由小到大
        for (int i = 0; i <= len - 1; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                // 高个子出列
                stack.pop();
            }

            // 这个元素
            ans[i] = stack.empty() ? -1 : stack.peek();

            // 压入i 接收后面身高的审判吧
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1, 0, 7};
        int[] arr01 = new int[]{0, 1, 2, 3, 4, 5, 7, 6};

        FindLeftFirstSmaller f1 = new FindLeftFirstSmaller();

        System.out.println(Arrays.toString(f1.work(arr)));
        System.out.println(Arrays.toString(f1.work(arr01)));
    }
}
